package com.hunter;


import java.util.List;

/*
链表题目
 */
public class LianBiaoTest {
    public class ListNode {
        // 存储节点的值
        int value;
        // 指向下一个节点的引用（相当于指针）
        ListNode next;

        ListNode() {
        }

        ListNode(int value) {
            this.value = value;
        }

        ListNode(int value, ListNode next) {
            this.value = value;
            this.next = next;
        }
    }

    /*
    反转单向链表（LeetCode 206）方法一
    思路：先设置新链表的第一个节点的值，
          再初始化旧链表的第一个节点
          判断旧节点是否为null
          如果不为null，
          简单而言，就是创建一个新链表的节点newHead，
          然后把旧链表节点oldHead的值给这个新创建的新链表节点newHead
          然后再将旧链表的下一个值赋予旧链表的oldHead
          如此反复操作，旧链表的值就被反转加入了新链表
     */
    private ListNode reverseList(ListNode head) {
        // 设置新链表第一个节点的value值，不用设置指针。
        ListNode newHead = null;
        // 旧链表的第一个节点
        ListNode oldHead = head;
        while (oldHead != null) {
            /*
            创建一个节点
            值为旧链表中的第一个链表的值
            下一个节点指向新链表的头部
            并且更新新链表的头部
            */
            newHead = new ListNode(oldHead.value, newHead); // 更新新链表
            /*
            旧链表中的元素变成下一个旧链表元素，
            */
            oldHead = oldHead.next; // 操作，调整旧链表
        }
        return newHead;
    }

    /*
    反转单向链表（LeetCode 206）方法二 递归
     */
    private ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head; // 最后节点
        }
        // 递归调用
        // last是末端节点（即反转之后的头节点）
        // 实现反转
        ListNode last = reverseList2(head.next);
        // 反转连接
        head.next.next = head;
        // 将当前节点的next设为null
        //（表示当前节点成了反转链表中的最后一个节点）
        head.next = null;
        return last;
        /*
        head.next.next = haed 的作用：
        把head -> head.next -> head.next.next
        变为head -> head.next -> head
        是将当前节点 p 的下一个节点的 next 指针指向 p，
        从而实现节点的反转。
        通过递归地调整节点连接，
        最终实现整个链表的反转。
         */
    }

    /*
   反转单向链表（LeetCode 206）方法三
    */
    // o1 旧头,n1 新头，o2旧老二
    private ListNode reverseList3(ListNode o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        // o1 -> o2 -> o3
        // n1 -> n2 -> n3

        // 初始化 o2 为当前节点 o1 的下一个节点
        ListNode o2 = o1.next;
        // 初始化 n1 为当前节点 o1，它将成为反转后的链表的头节点
        ListNode n1 = o1;
        while (o2 != null) {
            // 保存 o2 的下一个节点，以便下次迭代使用
            o1.next = o2.next;
            // 反转当前节点 o2 的连接，使其指向前一个节点 n1
            o2.next = n1;
            // 更新 n1 为当前节点 o2，使 o2 成为反转链表的新头节点
            n1 = o2;
            // 更新 o2 为之前保存的下一个节点，准备下一次迭代
            o2 = o1.next;
        }
        // 返回反转后的链表的头节点
        return n1;
    }

    /*
    链表  根据值删除节点 方法一
    疑问：为什么要创建虚拟头节点（哨兵节点）？
    思路：先创建一个虚拟头节点，简化代码逻辑，使删除操作更加统一和简洁。
          判断头节点p2是否为null，
          不为null，遍历链表，
          再判断头节点p2的值是否等于要删除值value
          等于就删除，即将p1.next 指向 p2.next，把p2指向p2.next
          如果p2的值不等于要删除值value，就将p1和p2都向后移动，继续遍历
          当 p2的值为null时，返回处理后的链表头节点，即s.next
     */
    private ListNode removeElements(ListNode head, int value) {
        // 创建新一个虚拟头节点 s，其 next 指向原始头节点 head
        ListNode s = new ListNode(-1, head);
        // 初始化 p1 为虚拟头节点 s，用于记录前一个有效节点
        ListNode p1 = s;
        // 初始化 p2 为原始头节点 head，用于遍历链表
        ListNode p2 = s.next;

        // 当头节点p2不为null时，继续遍历链表
        while (p2 != null) {
            // 当 p2的值 等于 给定要删除的值value
            if (p2.value == value) {
                // 将 p1的next指针 指向 p2的下一个节点，从而移除p2
                p1.next = p2.next;
                // p2 指向 p2的下一个节点，继续遍历
                p2 = p2.next;
            } else {
                // 如果当前 p2的值不为要删除的值，p1向后移动
                p1 = p1.next;
                // p2也向后移动，继续遍历
                p2 = p2.next;
            }
        }
        // 返回新的头节点 s 的下一个节点，即处理后的链表头节点
        return s.next;
    }

    /*
    链表  根据值删除节点 方法二 递归
     */
    private ListNode removeElements2(ListNode head, int value) {
        // 如果节点为空，直接返回null
        if (head == null) {
            return null;
        }
        // 递归处理下一个节点，更新当前节点的next指针
        head.next = removeElements(head.next, value);
        // 根据当前节点的值决定返回哪个节点
        if (head.value == value) {
            // 如果当前节点的值等于value，则返回下一个节点递归的结果
            return head.next;
        } else {
            // 如果当前节点的值不等于value，则返回当前节点
            return head;
        }
    }

    /*
    链表  删除倒数节点 递归
     */

    private int recursion(ListNode p, int n) {
        // p = null时，返回0，表示null在倒数第0个数字
        if (p == null) {
            return 0;
        }
        int nth = recursion(p.next, n);// 每个节点的下一个节点从末尾开始的位置
        System.out.println(p.value + " " + nth);// 打印当前节点的值和下一个节点从末尾开始的位置
        if (nth == n) {// 如果后面节点的位置正好是我们要删除的位置n
            // p=3  p.next=4  p.next.next=5
            p.next = p.next.next;// 跳过下一个节点，完成删除操作
        }
        return nth + 1;
    }

    private ListNode removeNthForEnd(ListNode head, int n) {
        // 创建一个新的虚拟头结点（哨兵节点），初始化为-1，指向原始头结点
        // 这样做可以在统一的地方处理删除操作，避免边界条件的复杂性
        ListNode s = new ListNode(-1, head);
        // 开始递归删除过程，传入虚拟头结点和要删除的倒数第n个节点
        recursion(s, n);
        // 返回新的头结点，忽略虚拟头结点本身
        // 此时虚拟头结点的下一个节点即为我们处理后的链表头结点
        return s.next;
    }

    /*
    链表  删除倒数节点（二）
     */
    private ListNode removeNthForEnd2(ListNode head, int n) {
        // 哨兵节点s
        ListNode s = new ListNode(-1, head);
        ListNode p1 = s;
        ListNode p2 = s;
        // 先让 p2 前进 n+1
        for (int i = 0; i < n + 1; i++) {
            p2 = p2.next;
        }
        // 让 p1和p2 一起前进，直到 p2为 null，这样 p1的下一个元素就是要删除的元素
        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;
        return s.next;
    }

    /*
    删除有序链表中的重复节点，留下一个
    有序链表的去重
     */
    private ListNode deleteDuplicates(ListNode head) {
        // 节点数 < 2
        if (head == null || head.next == null) {
            return head;
        }
        // 节点数 >= 2
        ListNode p1 = head;
        ListNode p2;
        while ((p2 = p1.next) != null) {
            if (p1.value == p2.value) {
                // 删除p2
                p1.next = p2.next;
            } else {
                // 向后平移
                p1 = p1.next;
            }
        }
        return head;
    }


    /*
    删除有序链表的重复节点，有重复的节点都删除
     */
    private ListNode deleteDuplicates2(ListNode p) {
        if (p == null || p.next == null) {
            return p;
        }
        if (p.value == p.next.value) {
            ListNode x = p.next.next;
            while (x != null && x.value == p.value) {
                x = x.next;
            }
            return deleteDuplicates2(x);
        }else {
            p.next = deleteDuplicates2(p.next);
            return p;
        }
    }


}
